package sol.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * Contains Duplicate II
 * Created by lkk on 2016/8/28.
 */
public class Issue219 {
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        //用来保存最近一次访问到的数字及其下标
        Map<Integer, Integer> visitedMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            int num = nums[i];
            if (visitedMap.containsKey(num) && (i - visitedMap.get(num)) <= k)
                return true;
            else
                visitedMap.put(num, i);
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 3};
        System.out.println(containsNearbyDuplicate(nums, 5));

    }
}
